package Leetcode.图;

/**
 * 任意两点之间是否存在长度为k的路径
 */
public class 任意两点之间是否存在长度为k的路径 {

    public boolean hasPathOfLengthK(int[][] graph, int u, int v, int k) {
        // 检查输入的合法性
        if (graph == null || graph.length == 0 || graph.length != graph[0].length) {
            return false;
        }
        int n = graph.length;
        // 使用一个布尔数组来标记顶点是否被访问
        boolean[] visited = new boolean[n];
        // 从顶点u开始深度优先搜索，寻找长度为k的路径到顶点v
        return dfs(graph, u, v, k, visited);
    }

    private boolean dfs(int[][] graph, int current, int destination, int remainingSteps, boolean[] visited) {
        // 如果当前顶点是目的地并且剩余步数为0，则找到了长度为k的路径
        if (current == destination) {
            return remainingSteps == 0;
        }
        // 如果剩余步数为负数或者当前顶点已被访问，则返回false
        if (remainingSteps < 0 || visited[current]) {
            return false;
        }
        // 标记当前顶点为已访问
        visited[current] = true;
        // 遍历所有顶点，尝试从当前顶点出发的所有可能路径
        for (int i = 0; i < graph.length; i++) {
            // 如果存在边且下一个顶点未被访问
            if (graph[current][i] == 1 && !visited[i]) {
                // 递归搜索下一个顶点
                if (dfs(graph, i, destination, remainingSteps - 1, visited)) {
                    return true;
                }
            }
        }
        // 回溯，取消当前顶点的访问标记
        visited[current] = false;
        return false;
    }

    public static void main(String[] args) {
        任意两点之间是否存在长度为k的路径 finder = new 任意两点之间是否存在长度为k的路径();
        int[][] graph = {
                {0, 1, 1, 0, 0},
                {1, 0, 1, 1, 0},
                {1, 1, 0, 1, 0},
                {0, 1, 1, 0, 1},
                {0, 0, 0, 1, 0}
        };
        int u = 0;
        int v = 4;
        int k = 3;
        boolean hasPath = finder.hasPathOfLengthK(graph, u, v, k);
        System.out.println("There is a path of length " + k + " from " + u + " to " + v + ": " + hasPath);
    }
}
